package leetcode

import kotlinetc.println

//https://leetcode.com/problems/subsets-ii/
/**
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Accepted
206,492
Submissions
484,180
 */
fun main(args: Array<String>) {


    subsetsWithDup(intArrayOf(1, 2, 2)).println()
}

/**
 * similar [subsets]  [permuteUnique]  [getPermutation]  [permute]
 * 用回溯，标记每个数字是否被访问过
 */
fun subsetsWithDup(nums: IntArray): List<List<Int>> {

    val visited = Array<Boolean>(nums.size) { false }

    nums.sort()

    val result = ArrayList<List<Int>>()
    val list = ArrayList<Int>()

    subsetsWithDupRecursive(result, nums, list, 0, visited)

    return result
}


//Classic 非常具有代表性的题目，这里回溯的位置非常细腻
/**
 *
 */
fun subsetsWithDupRecursive(result: ArrayList<List<Int>>, nums: IntArray, list: ArrayList<Int>, level: Int, visited: Array<Boolean>) {
    if (level == nums.size) {
        result.add(ArrayList(list))
        return
    }


    list.add(nums[level])
    visited[level] = true
    subsetsWithDupRecursive(result, nums, list, level + 1, visited)



    list.removeAt(list.size - 1)
    visited[level] = false

    //和permuteUnique那题很像，但是回溯的位置究竟放在哪里需要思考仔细

    //对于中间 重复数字  不允许修改之前的visited 状态，避免重复  2 2 2 2  只允许从前往后 依次增加 0000  1000 1100 1110 1111
    //这里直接return　重复数字不允许反转　状态
    if (level - 1 >= 0 && nums[level - 1] == nums[level] && visited[level - 1]) return

    subsetsWithDupRecursive(result, nums, list, level + 1, visited)
}
